This is a phase Ia/Ib study to evaluate the toxicity and immunologic response following administration of the recombinant vaccinia-CEA vaccine to patients with resected colorectal cancer who have no evidence of disease but are at high risk for disease recurrence.